package com.dexter.year2023.charpter2_reverselinklist.level2.topic2_5再论回文序列;

import com.dexter.year2023.charpter1_linkedlist.level1.Demo1.Node;

import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.initLinkedList;

/**
 * 第一关-第二节（白银）-2.2-回文序列-法7
 */
public class IsPalindromeByTwoPoints {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 4, 3, 2, 1};
        Node head = initLinkedList(a);
        boolean res = isPalindromeByTwoPoints(head);
        System.out.println("是否为回文序列：" + (res ? "是" : "否"));
    }

    public static boolean isPalindromeByTwoPoints(Node head) {
        // 判空
        if (head == null || head.next == null) {
            return true;
        }
        // 定义快慢指针，找一半
        Node slow = head, fast = head;
        // 定义prepre pre，反转前一半
        Node prepre = null, pre = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            // slow 一步，fast 两步
            slow = slow.next;
            fast = fast.next.next;
            // 反转链表
            pre.next = prepre;
            prepre = pre;
        }
        // 奇数个数，slow现在中间，要走到回文的后一半
        if (fast != null) {
            slow = slow.next;
        }
        // pre是前一半反转的4321 和 slow现在的后一半4321 进行比较
        while (pre != null && slow != null) {
            if (pre.val != slow.val) {
                return false;
            }
            pre = pre.next;
            slow = slow.next;
        }
        return true;
    }
}
